#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>


/**
*假如你有一个用1001个整数组成的数组，这些整数是任意排列的，
但是你知道所有的整数都在1到1000之间（包括1000）、
此外，除了一个数字出现两次外，其他的数字只出现了一次。
假设你对数组做一次处理，用一种算法找出重复的那个数字，
要求不使用大量额外的存储空间（即要求辅助空间为O(1)）

*/
//如果两个相同的数求异或，那么结果为0。
//0与一个数异或的结果就是这个数


int FindNum(int* a)
{
	int k = a[0];
	int i = 1;
	for (i = 1; i <= 1000; i++)//数组中的元素与1-1000元素异或，其他的都消了，只剩一个重复的数字
	{
		k ^= (a[i] ^ i);
	}
	return k;
}


int main()
{
	int a[1001] = { 0 };
	for (int i = 0; i <= 999; i++)
	{
		a[i] = i + 1;//生成1000个数且是1 - 1000 下标为a[0] - a[999]
	}
	a[1000] = rand() % 1000;
	//0 ~ 1000 有1001个数字
	printf("%d is %d\n", a[1000], FindNum(a));
	return 0;
}


